package com.example;

import java.util.*;

/**
 * @Author loubobooo
 * @Description #102. 二叉树的层次遍历
 * @Date 2020/3/24
 */
public class BinaryTreeLevelorderTraversal {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    LinkedList<List<Integer>> lists = new LinkedList<>();

    /**
     * 方法描述:给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     * 示例 1：
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     * @param: [root]
     * @return: java.util.List<java.util.List<java.lang.Integer>>
     * @author: loubobooo
     * @date: 2022/2/25
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return lists;
        }

        bfs(root, 0);
        return lists;
    }

    /**
     * @return
     * @Author loubobooo
     * @Description 广度优先遍历
     * @Date 2020/3/24 16:31
     * @Param
     **/
    private void bfs(TreeNode node, Integer level) {
        if (node == null) {
            return;
        }
        if (level == lists.size()) {
            // 先存入空数组
            lists.add(new ArrayList<>());
        }
        // 广度优先遍历
        bfs(node.left, level + 1);
        bfs(node.right, level + 1);
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        if(root == null){
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while (count > 0){
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if(poll.left != null){
                    queue.add(poll.left);
                }
                if(poll.right != null){
                    queue.add(poll.right);
                }
                count--;
            }
            lists.add(list);
        }
        return lists;
    }

}
